'''
Created on Jul 18, 2011

@author: anupams
'''
from com.anupam.graphs.GraphsAnupam import SampleGraphObject

class BreadthFirstSearch(object):
  """
    Performs breadth first search on the graph
  """

  def __init__(self, graphDict, nodes):
    """
    Default constructor of the class.
    
    Args:
      graphDict : Adjucancy list of the graph
      nodes : graph node objects @see{ColoredGraphNode}
    """
    self.graphDict = graphDict
    self.nodes = nodes
    pass

  def doBFS(self, rootKey):
    """
    Perfroms a breadth first search on the provided adjucancy list of the graph.
      Args :
        rootKey : Starting node that is to be treated as graph root
    """
    nodeQueue = []
    nodeQueue.append(rootKey)
    print nodeQueue

    while len(nodeQueue):

      topElement = nodeQueue.pop(0)
      nodeObj = self.nodes[topElement]
      nodeObj.color = 'black'
      adjucancyList = self.graphDict[topElement]

      for i in range(0, len(adjucancyList)):

        childNodeName = adjucancyList[i]
        childNodeObj = self.nodes[childNodeName]

        if childNodeObj.color == 'white':
          childNodeObj.color = 'grey'
          nodeQueue.append(childNodeName)

        childNodeObj.parents.append(topElement)
        nodeObj.children.append(childNodeName)

      print nodeQueue


if __name__ == '__main__':
  biDirGraphSample = SampleGraphObject()
  graphDict = biDirGraphSample.biDirGraphSample()
  traverse = BreadthFirstSearch(graphDict, biDirGraphSample.nodes)
  traverse.doBFS('s')
